package code.notdo;

import java.util.ArrayList;
import java.util.List;

/**
 * author : yeswater
 * date : 2023/12/7
 */

public class T042 {
    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(height));
    }
    
    public static int trap(int[] height) {
        int sum = 0;
        List<Integer> list = new ArrayList<>(); // 记录索引
        if (height.length < 3) {
            return sum;
        }
        // 边界
        if (height[0] > height[1]) {
            list.add(0);
        }
        if (height[height.length - 1] > height[height.length - 2]) {
            list.add(height.length - 1);
        }
        for (int i = 1; i < height.length - 1; i++) {
            // 高点
            if (height[i - 1] < height[i] && height[i] > height[i + 1]) {
                list.add(i);
            }
        }
        for (int i = 0; i < list.size() - 1; i++) {
            Integer l = list.get(i);
            Integer r = list.get(i + 1);
            
            int top = Math.min(height[l], height[r]);
            sum += getSum(height, top, l, list.get(i + 1));
        }
        return sum;
    }
    
    public static int getSum(int[] height, int top, int l, int r) {
        int sum = 0;
        for (int i = l; i <= r; i++) {
            if (top > height[i]) {
                sum += top - height[i];
            }
        }
        return sum;
    }
}
